#include<iostream>
#include<vector>
using namespace  std;
//第一种方法：
class Solution1 {
public:
    void rotate(vector<vector<int>>& matrix) {
        //第一种方法使用额外的数组来进行辅助，分析旋转前和旋转后的坐标
        //假设矩阵有n行，那么第i行在翻转90之后就变成了第n-1-i列
        //而第j列在翻转后就变成了第i行
        //由此就能够分析出矩阵旋转前后的位置映射公式
        //matrix[i][j] = matrix[j][n-1-i]
        //这样额外拿出一个二维空间再套用这个公式就能够解决这个问题
        int n = matrix.size();
        vector<vector<int>> ret(n,vector<int>(n));
        for(int i = 0;i<n;i++)
        {
            for(int j = 0;j<n;j++)
            {
                ret[j][n-1-i] = matrix[i][j];//[i,j]这个位置的值在替换之后就变到了另外一个位置
            }
        }
        matrix = ret;
    }
};
//第二种方法O(1)时间复杂度
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        //遍历起点
        int n = matrix.size();
        for(int i = 0;i<n/2;i++)
        {
            for(int j = 0;j<(n+1)/2;j++)
            {
                // 暂存 A 至 tmp
                int tmp = matrix[i][j];
                // 元素旋转操作 A <- D <- C <- B <- tmp
                matrix[i][j] = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = tmp;
            }
        }
    }
};